{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Equivalent Domino Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numEquivDominoPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #等价多米诺骨牌对的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由一些多米诺骨牌组成的列表&nbsp;<code>dominoes</code>。</p>\n",
    "\n",
    "<p>如果其中某一张多米诺骨牌可以通过旋转 <code>0</code>&nbsp;度或 <code>180</code> 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。</p>\n",
    "\n",
    "<p>形式上，<code>dominoes[i] = [a, b]</code>&nbsp;和&nbsp;<code>dominoes[j] = [c, d]</code>&nbsp;等价的前提是&nbsp;<code>a==c</code>&nbsp;且&nbsp;<code>b==d</code>，或是&nbsp;<code>a==d</code> 且&nbsp;<code>b==c</code>。</p>\n",
    "\n",
    "<p>在&nbsp;<code>0 &lt;= i &lt; j &lt; dominoes.length</code>&nbsp;的前提下，找出满足&nbsp;<code>dominoes[i]</code> 和&nbsp;<code>dominoes[j]</code>&nbsp;等价的骨牌对 <code>(i, j)</code> 的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>dominoes = [[1,2],[2,1],[3,4],[5,6]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= dominoes.length &lt;= 40000</code></li>\n",
    "\t<li><code>1 &lt;= dominoes[i][j] &lt;= 9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-equivalent-domino-pairs](https://leetcode.cn/problems/number-of-equivalent-domino-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-equivalent-domino-pairs](https://leetcode.cn/problems/number-of-equivalent-domino-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[2,1],[3,4],[5,6]]', '[[1,2],[1,2],[1,1],[1,2],[2,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        for i in range(len(dominoes)-1):\n",
    "            cnt = 0\n",
    "            if i >= len(dominoes):\n",
    "                break\n",
    "            for j in range(len(dominoes)-1,i,-1):\n",
    "                if dominoes[i][0] == dominoes[j][0] and dominoes[i][1] == dominoes[j][1]:\n",
    "                    cnt += 1\n",
    "                    del dominoes[j]\n",
    "                elif dominoes[i][0] == dominoes[j][1] and dominoes[i][1] == dominoes[j][0]:\n",
    "                    cnt += 1\n",
    "                    del dominoes[j]\n",
    "            count += int(cnt*(cnt+1)/2)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        # 暴力\n",
    "\n",
    "        # 哈希\n",
    "        ans = 0\n",
    "        dp = {}\n",
    "        for i, j in dominoes:\n",
    "            if (i, j) in dp:\n",
    "                ans += dp.get((i,j), 0)\n",
    "            dp[(i, j)] =dp.get((i,j),0) + 1\n",
    "            if i != j:\n",
    "                dp[(j, i)] =dp.get((j,i),0) + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        d = dict()\n",
    "        for do in dominoes:\n",
    "            k = min(do[0],do[1])\n",
    "            v = max(do[0],do[1])\n",
    "            if k not in d:\n",
    "                d[k] = dict()\n",
    "            if v not in d[k]:\n",
    "                d[k][v] = 1\n",
    "            else:\n",
    "                d[k][v] += 1\n",
    "        res = 0\n",
    "        for k in d:\n",
    "            for v in d[k]:\n",
    "                n = d[k][v]\n",
    "                res += n * (n-1)//2\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        将所有牌旋转到a < b\n",
    "        然后对a和b排序\n",
    "        然后从左到右统计某个牌一样大小的数量\n",
    "        相同的牌如果有n张，等价牌对就是(n^2 - n)/2张\n",
    "        \"\"\"\n",
    "        for x in dominoes:\n",
    "            x.sort()\n",
    "        dominoes.sort(key=lambda x: (x[0], x[1]))\n",
    "        first = 0\n",
    "        last = 0\n",
    "        count = 0\n",
    "        result = 0\n",
    "        for x in dominoes:\n",
    "            if x[0] != first or x[1] != last:\n",
    "                result += count * (count - 1) // 2\n",
    "                first = x[0]\n",
    "                last = x[1]\n",
    "                count = 1\n",
    "            else:\n",
    "                count += 1\n",
    "        result += count * (count - 1) // 2\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 暴力循环，会超时\n",
    "# class Solution:\n",
    "#     def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "#         result = 0\n",
    "#         length = len(dominoes)\n",
    "#         for i in range(length):\n",
    "#             for k in range(i+1,length):\n",
    "#                 if dominoes[i] == dominoes[k]:\n",
    "#                     result += 1\n",
    "#                 if dominoes[i][0] == dominoes[k][1] and dominoes[i][1] == dominoes[k][0] and dominoes[k][0] != dominoes[k][1]:\n",
    "#                     result += 1    \n",
    "#                 #if j == dominoes[k] and dominoes[k][0] != dominoes[k][1]:\n",
    "\n",
    "#         return result\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        result = 0\n",
    "        length = len(dominoes)\n",
    "\n",
    "        if len(dominoes) == 0:\n",
    "            return 0\n",
    "\n",
    "        for i in range(length-1):\n",
    "            if i>= len(dominoes):\n",
    "                break\n",
    "            cnt = 0\n",
    "            for k in range(len(dominoes)-1,i,-1):\n",
    "                if dominoes[i][0] == dominoes[k][0] and dominoes[i][1] == dominoes[k][1]:\n",
    "                    cnt += 1\n",
    "                    del dominoes[k]\n",
    "                elif dominoes[i][0] == dominoes[k][1] and dominoes[i][1] == dominoes[k][0]:\n",
    "                    cnt += 1\n",
    "                    del dominoes[k]   \n",
    "            result += int(cnt*(cnt+1)/2)\n",
    "        return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 解法1\n",
    "'''Note:超出时间限制'''\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        count=0\n",
    "        for i in range(len(dominoes)-1):\n",
    "            for j in range(i+1,len(dominoes)):\n",
    "                dominoes[i].sort()\n",
    "                dominoes[j].sort()\n",
    "                if dominoes[i]==dominoes[j]:\n",
    "                    count+=1\n",
    "        return count\n",
    "\n",
    "# 解法2：Hash表法\n",
    "'''思路：关键是key的选择。可以采取这样一种做法，将dominoes[i]的两个数拼凑成一个两位数，用这个两位数当key'''\n",
    "import collections\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self,dominoes):\n",
    "        Hash=collections.defaultdict(int)\n",
    "        res=0\n",
    "        for i,j in dominoes:\n",
    "            num=i*10+j if i>j else j*10+i\n",
    "            Hash[num]+=1\n",
    "        for i in Hash.values():\n",
    "            res+=i*(i-1)//2\n",
    "        return res\n",
    "\n",
    "\n",
    "# 解法2：删除法\n",
    "'''Note:思路：从前往后、从后往前遍历，当搜寻到相同item时就删除掉那个item.最后个数为 i*(i-1)//2'''\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self,dominoes):\n",
    "        if len(dominoes)==0 or len(dominoes[0])==0:\n",
    "            return 0\n",
    "        pairNum=0\n",
    "        for i in range(len(dominoes)):\n",
    "            cnt=0\n",
    "            if i>len(dominoes):    # 由于循环的过程中进行了元素删除，需要防止溢出\n",
    "                break\n",
    "            for j in range(len(dominoes)-1,i,-1):\n",
    "                if dominoes[i][0] == dominoes[j][0] and dominoes[i][1] == dominoes[j][1]:\n",
    "                    cnt+=1\n",
    "                    del dominoes[j]\n",
    "                elif dominoes[i][0] == dominoes[j][1] and dominoes[i][1] == dominoes[j][0]:\n",
    "                    cnt+=1\n",
    "                    del dominoes[j]\n",
    "            pairNum+=cnt*(cnt+1)//2\n",
    "        return pairNum\n",
    "\n",
    "\n",
    "#         if len(dominoes) == 0 or len(dominoes[0]) == 0:\n",
    "#             return 0\n",
    "        \n",
    "#         pairNum = 0\n",
    "        \n",
    "#         for i in range(len(dominoes)-1):\n",
    "#             cnt = 0\n",
    "#             if i >= len(dominoes):# 因为我们有删除操作，所以dominoes的长度小了，i会超出索引值\n",
    "#                 break\n",
    "#             for j in range(len(dominoes)-1, i, -1):# 从最后一张牌向前遍历，直到i+1\n",
    "#                 if dominoes[i][0] == dominoes[j][0] and dominoes[i][1] == dominoes[j][1]:\n",
    "#                     cnt += 1\n",
    "#                     del dominoes[j]\n",
    "#                 elif dominoes[i][0] == dominoes[j][1] and dominoes[i][1] == dominoes[j][0]:\n",
    "#                     cnt += 1\n",
    "#                     del dominoes[j]\n",
    "#             pairNum += int(cnt*(cnt+1)/2)\n",
    "#         return pairNum\n",
    "    \n",
    "\n",
    "# 作者：coldme-2\n",
    "# 链接：https://leetcode-cn.com/problems/number-of-equivalent-domino-pairs/solution/deng-jie-duo-mi-nuo-gu-pai-by-coldme-2/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        if len(dominoes) == 0 or len(dominoes[0]) == 0:\n",
    "            return 0\n",
    "        pairNum = 0\n",
    "        for i in range(len(dominoes)-1):\n",
    "            cnt = 0\n",
    "            if i >= len(dominoes):\n",
    "                break\n",
    "            for j in range(len(dominoes)-1, i, -1):\n",
    "                if dominoes[i][0] == dominoes[j][0] and dominoes[i][1] == dominoes[j][1]:\n",
    "                    cnt += 1\n",
    "                    del dominoes[j]\n",
    "                elif dominoes[i][0] == dominoes[j][1] and dominoes[i][1] == dominoes[j][0]:\n",
    "                    cnt += 1\n",
    "                    del dominoes[j]\n",
    "            pairNum += int(cnt*(cnt+1)/2)\n",
    "        return pairNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:    \n",
    "        ans = 0    \n",
    "        for i in range(len(dominoes)-1):\n",
    "            cnt = 0\n",
    "            if i >= len(dominoes):\n",
    "                break\n",
    "            for j in range(len(dominoes)-1, i, -1):\n",
    "                if dominoes[i][0] == dominoes[j][0] and dominoes[i][1] == dominoes[j][1]:\n",
    "                    cnt += 1\n",
    "                    del dominoes[j]\n",
    "                elif dominoes[i][0] == dominoes[j][1] and dominoes[i][1] == dominoes[j][0]:\n",
    "                    cnt += 1\n",
    "                    del dominoes[j]\n",
    "            ans += int(cnt*(cnt + 1) / 2)\n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for a,b in dominoes:\n",
    "            if a > b: dic[a * 10 + b] += 1\n",
    "            else: dic[b * 10 + a] += 1\n",
    "        res = 0\n",
    "        for val in dic.values():\n",
    "            if val > 1: res += val * (val - 1) // 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        \n",
    "        if len(dominoes) == 0 or len(dominoes[0]) == 0:\n",
    "            return 0\n",
    "        \n",
    "        pairNum = 0\n",
    "        \n",
    "        for i in range(len(dominoes)-1):\n",
    "            cnt = 0\n",
    "            if i >= len(dominoes):# 因为我们有删除操作，所以dominoes的长度小了，i会超出索引值\n",
    "                break\n",
    "            for j in range(len(dominoes)-1, i, -1):# 从最后一张牌向前遍历，直到i+1\n",
    "                if dominoes[i][0] == dominoes[j][0] and dominoes[i][1] == dominoes[j][1]:\n",
    "                    cnt += 1\n",
    "                    del dominoes[j]\n",
    "                elif dominoes[i][0] == dominoes[j][1] and dominoes[i][1] == dominoes[j][0]:\n",
    "                    cnt += 1\n",
    "                    del dominoes[j]\n",
    "            pairNum += int(cnt*(cnt+1)/2)\n",
    "        return pairNum\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        dominoes.sort(key = lambda x:[sum(x),max(x)])\n",
    "        for i in range(len(dominoes)):\n",
    "            a = sum(dominoes[i])\n",
    "            b = dominoes[i][::-1]\n",
    "            c = dominoes[i]\n",
    "            for j in range(i+1,len(dominoes)):\n",
    "                if sum(dominoes[j]) < a:\n",
    "                    continue\n",
    "                if sum(dominoes[j]) == a:\n",
    "                    if c == dominoes[j] or b == dominoes[j]:\n",
    "                        ans+=1 \n",
    "                    elif max(dominoes[j])>max(c):\n",
    "                        break\n",
    "                    continue\n",
    "                if sum(dominoes[j]) > a:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        if len(dominoes)==0:\n",
    "            return 0\n",
    "        tmp=[]\n",
    "        for i in dominoes:\n",
    "            i.sort()\n",
    "            tmp.append(str(i))\n",
    "        restmp=set(tmp)\n",
    "        #print(tmp)\n",
    "        count=0\n",
    "        num=0\n",
    "        for i in restmp:\n",
    "            count=tmp.count(i)\n",
    "            if count>=2:\n",
    "                num+=count*(count-1)//2\n",
    "        return num        \n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        for i,d in enumerate(dominoes):\n",
    "            d.sort()\n",
    "            dominoes[i] = tuple(d)\n",
    "        cnt = collections.Counter(dominoes)\n",
    "        res = 0\n",
    "        for v in cnt.values():\n",
    "            if v>=2:\n",
    "                res += v*(v-1)//2\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        m = {}\n",
    "        for dominoe in dominoes:\n",
    "            lower = min(dominoe)\n",
    "            upper = max(dominoe)\n",
    "            t = lower * 10 + upper\n",
    "            if t in m:\n",
    "                m[t] += 1\n",
    "            else:\n",
    "                m[t] = 1\n",
    "        r = 0\n",
    "        for v in m.values():\n",
    "            r += v * (v - 1) // 2\n",
    "        return r\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        cnts = Counter()\n",
    "        for a, b in dominoes:\n",
    "            if a < b: cnts[(a, b)] += 1\n",
    "            else: cnts[(b, a)] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        # C_n^2 = n * (n - 1) // 2\n",
    "        for val in cnts.values():\n",
    "            ans += val * (val - 1) // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        f={}\n",
    "        cc=0\n",
    "        for i , j in dominoes:\n",
    "            if i >j:\n",
    "                i,j=j,i\n",
    "            h=(i,j)\n",
    "            if h in f:\n",
    "                f[h]+=1\n",
    "            else:\n",
    "                f[h]=1\n",
    "        for i in f:\n",
    "            cc+=(f[i]*(f[i]-1))//2\n",
    "        return  cc\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        f,res = {},0\n",
    "        for x,y in dominoes:\n",
    "            if x>y:\n",
    "                x,y = y,x \n",
    "            tmp = x*10+y\n",
    "            if tmp not in f:\n",
    "                f[tmp] = 0\n",
    "            res += f[tmp]\n",
    "            f[tmp] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        dict = {}\n",
    "        for i in dominoes:\n",
    "            if i[0]>i[1]:\n",
    "                num = i[0]*10+i[1]\n",
    "            else:\n",
    "                num = i[1]*10+i[0]\n",
    "            if num in dict:\n",
    "                dict[num]+=1\n",
    "            else:\n",
    "                dict[num]=1\n",
    "        all = 0\n",
    "        for k in dict.values():\n",
    "            all+=k*(k-1)//2\n",
    "        return all"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\r\n",
    "        \r\n",
    "        domino_set = []\r\n",
    "        domino_sumer = [0 for i in dominoes]\r\n",
    "\r\n",
    "        for i in range(0,len(dominoes)):\r\n",
    "            if dominoes[i] not in domino_set:\r\n",
    "                domino_set.append(dominoes[i])\r\n",
    "                domino_set.append([dominoes[i][1],dominoes[i][0]])\r\n",
    "                domino_sumer[i] = dominoes.count(dominoes[i])  -1 \r\n",
    "                if dominoes[i][0] != dominoes[i][1]:\r\n",
    "                    domino_sumer[i] += dominoes.count([dominoes[i][1],dominoes[i][0]])\r\n",
    "                \r\n",
    "                if domino_sumer[i] !=0 :\r\n",
    "                    temp_count = domino_sumer[i]-1\r\n",
    "                    for j in range(i+1,len(dominoes)):\r\n",
    "                        if self.sameDomio(dominoes[j],dominoes[i]):\r\n",
    "                            domino_sumer[j] = temp_count\r\n",
    "                            temp_count = temp_count -1  \r\n",
    "        print(domino_sumer)\r\n",
    "        \r\n",
    "        return sum(domino_sumer)\r\n",
    "                             \r\n",
    "        \r\n",
    "        \r\n",
    "        \r\n",
    "        # count = 0\r\n",
    "        # for i in range(len(dominoes)):\r\n",
    "        #     for j in range(i+1,len(dominoes)):\r\n",
    "        #         if self.sameDomio(dominoes[i],dominoes[j]):\r\n",
    "        #             count +=1 \r\n",
    "        \r\n",
    "        # return count\r\n",
    "        \r\n",
    "    def sameDomio(self, a, b):\r\n",
    "        if a == b or (a[1] == b[0] and a[0] == b[1]):\r\n",
    "            return True\r\n",
    "        else:\r\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        stands,cou=[],[]\n",
    "        res=0\n",
    "        for one in dominoes:\n",
    "            if one in stands:cou[stands.index(one)] +=1\n",
    "            else:\n",
    "                stands.append(one)\n",
    "                cou.append(1)\n",
    "        for i in range(len(stands)):\n",
    "            #print('1:',stands[i],'--',cou[i],end=' ')\n",
    "            if  stands[i][::-1] in stands[i+1:]:\n",
    "                n=cou[i]+cou[stands.index(stands[i][::-1])]\n",
    "                res += n*(n-1)//2\n",
    "                #print('2:',stands[i],'--',cou[i])\n",
    "            elif stands[i][0]==stands[i][1]:\n",
    "                n= cou[i]        \n",
    "                res += n*(n-1)//2\n",
    "                #print('3:',stands[i],'--',cou[i])               \n",
    "            else:\n",
    "                if  stands[i][::-1] not in stands : \n",
    "                    n= cou[i]        \n",
    "                    res += n*(n-1)//2\n",
    "                    #print('4:',stands[i],'--',cou[i])\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for a, b in dominoes:\n",
    "            if a != b:\n",
    "                ans += cnt[(a, b)] + cnt[(b, a)]\n",
    "            else:\n",
    "                ans += cnt[(a, b)]\n",
    "            cnt[(a, b)] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        n=len(dominoes)\n",
    "        dic={}\n",
    "        for i in range(n):\n",
    "            dominoes[i]=tuple(sorted(dominoes[i]))\n",
    "            if dominoes[i] in dic.keys():\n",
    "                dic[dominoes[i]]+=1\n",
    "            else:\n",
    "                dic[dominoes[i]]=1\n",
    "        count=0\n",
    "        for key,value in dic.items():\n",
    "            count+=(value*(value-1))//2\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        dset = {}\n",
    "        res = 0\n",
    "        for d in dominoes:\n",
    "            x, y = str(d[0]), str(d[1])\n",
    "            key = x + '_' + y\n",
    "            key2 = y + '_' + x\n",
    "            if key == key2:\n",
    "                res += dset.get(key, 0)\n",
    "            else:\n",
    "                res += dset.get(key, 0) + dset.get(key2, 0)\n",
    "            dset[key] = dset.get(key, 0) + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        num = [0] * 100\n",
    "        for x, y in dominoes:\n",
    "            val = (x * 10 + y if x <= y else y * 10 + x)\n",
    "            res += num[val]\n",
    "            num[val] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        h = {}\n",
    "        for dominoe in dominoes:\n",
    "            x,y = dominoe[0],dominoe[1]\n",
    "            if x > y:\n",
    "                x,y = y,x\n",
    "            s0 = (x,y)\n",
    "            if s0 in h:\n",
    "                h[s0] += 1\n",
    "            else:\n",
    "                h[s0] = 1\n",
    "        for i in h.values():\n",
    "            res += i * (i - 1)\n",
    "        return res // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        num = [0] * 100\n",
    "        ret = 0\n",
    "        for x, y in dominoes:\n",
    "            val = (x * 10 + y if x <= y else y * 10 + x)\n",
    "            ret += num[val]\n",
    "            num[val] += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        counter = Counter()\n",
    "        for domino in dominoes:\n",
    "            if domino[0]<=domino[1]:\n",
    "                counter[(domino[0],domino[1])]+=1\n",
    "            else:\n",
    "                counter[(domino[1],domino[0])]+=1\n",
    "        ans = 0\n",
    "        for index in counter:\n",
    "            if counter[index]>1:\n",
    "                ans += counter[index]*(counter[index]-1)//2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        result = {}\n",
    "        for v in dominoes:\n",
    "            newV = (min(*v), max(*v))\n",
    "            if newV not in result:\n",
    "                result[newV] = 1\n",
    "            else:\n",
    "                result[newV] += 1\n",
    "        count = 0\n",
    "        for v in result.values():\n",
    "            count += v*(v-1)//2\n",
    "        return count\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        # 多米诺骨牌使用二元对表示，等价是可以翻转两个二元对使元素一一对应\n",
    "        # 让每一个二元对都变为指定的格式，即第一维必须不大于第二维，这样等价仅需要判断两个二元对是否完全相同\n",
    "        # 将每一个二元对拼接成一个两位的正整数\n",
    "        num = [0] * 100\n",
    "        ret = 0\n",
    "        for x,y in dominoes:\n",
    "            val = (x * 10 + y if x <= y else y * 10 + x)\n",
    "            ret += num[val]\n",
    "            # 出现了相同的二元对则数量加一\n",
    "            num[val] += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        dic={x:0 for x in range(11,100)}\n",
    "        for d in dominoes:\n",
    "            dic[min(d[0],d[1])*10+max(d[0],d[1])]+=1\n",
    "        result=0\n",
    "        for x in dic:\n",
    "            if dic[x]>=2:\n",
    "                result+=dic[x]*(dic[x]-1)//2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        #把每个多米诺骨牌翻成小的数字在上，大的数字在下的情况，这样可以使相同的多米诺骨牌的状态也相同，便于统计数目。然后用哈希字典来统计每种多米诺骨牌的个数，最后遍历每种骨牌，用组合数学 n * (n - 1) // 2 求每种骨牌成对的数目，将其累加得到最后结果。\n",
    "\n",
    "\n",
    "        \n",
    "        ans = 0\n",
    "        d = dict()\n",
    "        for d1, d2 in dominoes:\n",
    "            # 排序后加入字典\n",
    "            index = tuple(sorted((d1, d2)))\n",
    "            if index in d:\n",
    "                d[index] += 1\n",
    "            else:\n",
    "                d[index] = 1\n",
    "        # 计算答案\n",
    "        for i in d:\n",
    "            ans += d[i] * (d[i] - 1) // 2\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        d = dict()\n",
    "        for d1, d2 in dominoes:\n",
    "            # 排序后加入字典\n",
    "            index = tuple(sorted((d1, d2)))\n",
    "            if index in d:\n",
    "                d[index] += 1\n",
    "            else:\n",
    "                d[index] = 1\n",
    "        # 计算答案\n",
    "        print(d)\n",
    "        for i in d:\n",
    "            ans += d[i] * (d[i] - 1) // 2\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        num = 0\n",
    "        ret = dict()\n",
    "        n = len(dominoes)\n",
    "        for i in range(n):\n",
    "            if dominoes[i][0] < dominoes[i][1]:\n",
    "                c = 10*dominoes[i][0] + dominoes[i][1]\n",
    "            else:\n",
    "                c = 10*dominoes[i][1] + dominoes[i][0]\n",
    "            \n",
    "            if c in ret:\n",
    "                num += ret[c]\n",
    "                ret[c] += 1\n",
    "            else:\n",
    "                ret[c] = 1\n",
    "\n",
    "        return num\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        count = {}\n",
    "        result = 0\n",
    "\n",
    "        for domino in dominoes:\n",
    "            key = str(sorted(domino))\n",
    "            if key in count:\n",
    "                result += count[key]\n",
    "                count[key] += 1\n",
    "            else:\n",
    "                count[key] = 1\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        # 方法一：回溯法。超时\n",
    "        # length = len(dominoes)\n",
    "        # result_list = []\n",
    "        # def tarceback(dominoes, path_list, limit):\n",
    "        #     if len(path_list) == limit:\n",
    "        #         if path_list[0] == path_list[1] or path_list[0] == path_list[1][::-1]:\n",
    "        #             tmep_list = path_list.copy()\n",
    "        #             #  错误点：一直向前所以不存在0,1和1，0的情况：[[1,2],[1,2],[1,1],[1,2],[2,2]]。共3种\n",
    "        #             result_list.append(tmep_list)\n",
    "        #         return\n",
    "        #     if not dominoes:\n",
    "        #         return\n",
    "        #     for i in range(len(dominoes)):\n",
    "        #         path_list.append(dominoes[i])\n",
    "        #         tarceback(dominoes[i+1:], path_list, limit)\n",
    "        #         path_list.pop()\n",
    "            \n",
    "        # if length == 1:\n",
    "        #     return 0\n",
    "        # elif length == 2:\n",
    "        #     if dominoes[0] == dominoes[1] or dominoes[0] == dominoes[1][::-1]:\n",
    "        #         return 1\n",
    "        #     else:\n",
    "        #         return 0\n",
    "        # else:\n",
    "        #     tarceback(dominoes, [], 2)\n",
    "        #     return len(result_list)\n",
    "\n",
    "        # 双层遍历\n",
    "        # length = len(dominoes)\n",
    "        # start = 0\n",
    "        # end = 1\n",
    "        # result_list = []\n",
    "        # while start < end < length:\n",
    "        #     if dominoes[end] in [dominoes[start], dominoes[start][::-1]]:\n",
    "        #         result_list.append([start, end])\n",
    "        #     end += 1\n",
    "        #     if end == length:\n",
    "        #         start += 1\n",
    "        #         end = start + 1\n",
    "        # print(result_list)\n",
    "        # return len(result_list)\n",
    "\n",
    "        result_dict = {}\n",
    "        for i in dominoes:\n",
    "            # 错误点：数字列表不能用.join()方法 temp_str = \"\".join(i) TypeError: sequence item 0: expected str instance, int found\n",
    "            i = map(str, i)\n",
    "            # 错误点：字典的键值不能为列表if i not in result_dict.keys() or i[::-1] not in result_dict.keys(): TypeError: unhashable type: 'list'\n",
    "            temp_str = \"_\".join(i)\n",
    "            if temp_str not in result_dict.keys() and temp_str[::-1] not in result_dict.keys():\n",
    "                result_dict[temp_str] = 1\n",
    "            elif temp_str in result_dict.keys():\n",
    "                result_dict[temp_str] += 1\n",
    "            elif temp_str[::-1] in result_dict.keys():\n",
    "                result_dict[temp_str[::-1]] += 1\n",
    "        print(result_dict)\n",
    "        count = 0\n",
    "        for v in result_dict.values():\n",
    "            count += v * (v - 1) // 2\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        dict1={}\n",
    "        for i in range(len(dominoes)):\n",
    "            temp1=str(dominoes[i][0])+str(dominoes[i][1])\n",
    "            temp2=temp1[::-1]\n",
    "            if temp1 in dict1:\n",
    "                dict1[temp1]+=1\n",
    "            elif temp2 in dict1:\n",
    "                dict1[temp2]+=1\n",
    "            else:\n",
    "                dict1[temp1]=1\n",
    "        aa=[i*(i-1)//2 for i in dict1.values() if i>=2]\n",
    "        return sum(aa) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        return sum(x * (x - 1) // 2 for x in Counter((a, b) if a <= b else (b, a) for a, b in dominoes).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\r\n",
    "        dic = {}\r\n",
    "        for i in dominoes:\r\n",
    "            if i[0] > i[1]:\r\n",
    "                i[0], i[1] = i[1], i[0]\r\n",
    "            if str(i[0]) + str(i[1]) not in dic:\r\n",
    "                dic[str(i[0]) + str(i[1])] = 1\r\n",
    "            else:\r\n",
    "                dic[str(i[0]) + str(i[1])] += 1\r\n",
    "        res = 0\r\n",
    "        for i in dic:\r\n",
    "            res += dic[i] * (dic[i] - 1) // 2\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        return sum(x * (x - 1) // 2 for x in Counter(a**3+b**3 for a, b in dominoes).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        for i in range(len(dominoes)):\n",
    "            dominoes[i].sort()\n",
    "        dominoes.sort()\n",
    "        print(dominoes)\n",
    "        q=0\n",
    "        num1=0\n",
    "        for j in range(len(dominoes)-1):\n",
    "            if dominoes[j]==dominoes[j+1]:\n",
    "                q=q+1\n",
    "                num1=num1+q\n",
    "            else:\n",
    "                q=0\n",
    "        return num1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        n=len(dominoes)\n",
    "        res=0\n",
    "        for i in range(len(dominoes)):\n",
    "            #tmp用来记录与当前牌等价的牌的数量\n",
    "            tmp=1\n",
    "            for j in range(len(dominoes)-1,i,-1):\n",
    "                if (dominoes[i][0]==dominoes[j][0] and dominoes[i][1]==dominoes[j][1]) or (dominoes[i][0]==dominoes[j][1] and dominoes[i][1]==dominoes[j][0]):\n",
    "                    tmp+=1\n",
    "                    del dominoes[j]\n",
    "            if tmp>1:\n",
    "                res+=tmp*(tmp-1)//2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        num = 0\n",
    "        i = 0\n",
    "        max = 0\n",
    "        while i<len(dominoes):\n",
    "            j = i+1\n",
    "            while j<len(dominoes):\n",
    "                if dominoes[i]==dominoes[j] or (dominoes[i][0]==dominoes[j][1] and dominoes[i][1]==dominoes[j][0]):\n",
    "                    max+=1\n",
    "                    dominoes.pop(j)\n",
    "                else:\n",
    "                    j+=1\n",
    "            i+=1\n",
    "            num += (max+1)*max//2\n",
    "            max=0\n",
    "        return num\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # num = 0\n",
    "        # x = len(dominoes)\n",
    "        # for i in range(x):\n",
    "        #     for j in range(i+1,x):\n",
    "        #         if dominoes[i][0]==dominoes[j][0] and dominoes[i][1]==dominoes[j][1]:\n",
    "        #             num +=1\n",
    "        #         else:\n",
    "        #             if dominoes[i][0]==dominoes[j][1] and dominoes[i][1]==dominoes[j][0]:\n",
    "        #                 num +=1\n",
    "        # return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        for item in dominoes:\n",
    "            item[0], item[1] = min(item[0], item[1]), max(item[0], item[1])\n",
    "        \n",
    "        count = 0\n",
    "        while dominoes:\n",
    "            dominoe = dominoes.pop(0)\n",
    "            pre = 1\n",
    "            while True:\n",
    "                try:\n",
    "                    dominoes.remove(dominoe)\n",
    "                    pre += 1\n",
    "                except:\n",
    "                    count += pre * (pre - 1) // 2\n",
    "                    break\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        for item in dominoes:\n",
    "            item[0], item[1] = min(item[0], item[1]), max(item[0], item[1])\n",
    "        \n",
    "        count = 0\n",
    "        while dominoes:\n",
    "            dominoe = dominoes.pop(0)\n",
    "            pre = 1\n",
    "            while True:\n",
    "                try:\n",
    "                    dominoes.remove(dominoe)\n",
    "                    pre += 1\n",
    "                except:\n",
    "                    count += pre * (pre - 1) // 2\n",
    "                    break\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        n = len(dominoes)\n",
    "        sumToIdx = {}\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            temp_sum = sum(dominoes[i])\n",
    "            if temp_sum not in sumToIdx:\n",
    "                sumToIdx[temp_sum] = []\n",
    "            else:\n",
    "                for j in sumToIdx[temp_sum]:\n",
    "                    if (dominoes[j][0] == dominoes[i][0] and dominoes[j][1] == dominoes[i][1]) or (dominoes[j][0] == dominoes[i][1] and dominoes[j][1] == dominoes[i][0]):\n",
    "                        count += 1\n",
    "            sumToIdx[temp_sum].append(i)\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        dominoes = [tuple(sorted(l)) for l in dominoes]\n",
    "        d = collections.Counter(dominoes)\n",
    "        ans = 0\n",
    "        for key in d:\n",
    "            if d[key] > 1:\n",
    "                n = d[key]\n",
    "                ans += int((n**2-n)/2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        a = Counter([tuple(sorted(i)) for i in dominoes])\n",
    "        res = 0\n",
    "        for k, v in a.items():\n",
    "            if v > 1:\n",
    "                res += reduce(mul, range(v-1, v + 1)) // 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        if len(dominoes) == 0 or len(dominoes[0]) == 0:\n",
    "            return 0\n",
    "        \n",
    "        pairNum = 0\n",
    "        \n",
    "        for i in range(len(dominoes)-1):\n",
    "            cnt = 0\n",
    "            if i >= len(dominoes):# 因为我们有删除操作，所以dominoes的长度小了，i会超出索引值\n",
    "                break\n",
    "            for j in range(len(dominoes)-1, i, -1):# 从最后一张牌向前遍历，直到i+1\n",
    "                if dominoes[i][0] == dominoes[j][0] and dominoes[i][1] == dominoes[j][1]:\n",
    "                    cnt += 1\n",
    "                    del dominoes[j]\n",
    "                elif dominoes[i][0] == dominoes[j][1] and dominoes[i][1] == dominoes[j][0]:\n",
    "                    cnt += 1\n",
    "                    del dominoes[j]\n",
    "            pairNum += int(cnt*(cnt+1)/2)\n",
    "        return pairNum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        n = len(dominoes)\n",
    "        for i in range(n):\n",
    "            if dominoes[i][0] > dominoes[i][1]:\n",
    "                temp = dominoes[i][0]\n",
    "                dominoes[i][0] = dominoes[i][1]\n",
    "                dominoes[i][1] = temp\n",
    "        self.quick_sort(dominoes)\n",
    "        count = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            j = i + 1\n",
    "            while j < n:\n",
    "                if dominoes[i] == dominoes[j]:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    break\n",
    "            count += int((j - i) * (j - i - 1) / 2)\n",
    "            i = j\n",
    "        return count\n",
    "\n",
    "    def quick_sort(self, arr, left=None, right=None):\n",
    "        if left == None:\n",
    "            left = 0\n",
    "        if right == None:\n",
    "            right = len(arr) - 1\n",
    "        if left < right:\n",
    "            partition_index = self.partition(arr, left, right)\n",
    "            self.quick_sort(arr, left, partition_index - 1)\n",
    "            self.quick_sort(arr, partition_index + 1, right)\n",
    "\n",
    "    def partition(self, arr, left, right):\n",
    "        pivot = left\n",
    "        index = pivot + 1\n",
    "        i = index\n",
    "        while i <= right:\n",
    "            if arr[i][0] < arr[pivot][0] or (arr[i][0] == arr[pivot][0] and arr[i][1] < arr[pivot][1]):\n",
    "                temp = arr[i]\n",
    "                arr[i] = arr[index]\n",
    "                arr[index] = temp\n",
    "                index += 1\n",
    "            i += 1\n",
    "        temp = arr[pivot]\n",
    "        arr[pivot] = arr[index - 1]\n",
    "        arr[index - 1] = temp\n",
    "        return index - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        combination = lambda n:n*(n-1)/2\n",
    "        for i in range(len(dominoes)):\n",
    "            if(dominoes[i][0]>dominoes[i][1]):\n",
    "                dominoes[i]=dominoes[i][0]*10+dominoes[i][1]\n",
    "            else:\n",
    "                dominoes[i]=dominoes[i][0]+dominoes[i][1]*10\n",
    "        dominoes.sort()\n",
    "        result = 1\n",
    "        s=0\n",
    "        for i in range(1, len(dominoes)):\n",
    "            if dominoes[i]==dominoes[i-1]:\n",
    "                result+=1\n",
    "            else:\n",
    "                s+=combination(result)\n",
    "                result=1\n",
    "        s+=combination(result)\n",
    "        return int(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        def add(n):\n",
    "            result=n\n",
    "            if n!=0:\n",
    "               result+=add(n-1) \n",
    "            return result\n",
    "        \n",
    "        store={}\n",
    "\n",
    "        while True:\n",
    "            if len(dominoes)<=1:\n",
    "                break\n",
    "            strTag=str(dominoes[0][0])+\",\"+str(dominoes[0][1])\n",
    "            store[strTag]=[]\n",
    "            temp=dominoes[0]\n",
    "            del dominoes[0]\n",
    "            item=0\n",
    "            while True:\n",
    "                if item>=len(dominoes):\n",
    "                    break\n",
    "                if (dominoes[item][0]==temp[0] and dominoes[item][1]==temp[1]) or (dominoes[item][1]==temp[0] and dominoes[item][0]==temp[1]):\n",
    "                    store[strTag].append(dominoes[item])\n",
    "                    del dominoes[item]\n",
    "                    #print(dominoes)\n",
    "                    item-=1\n",
    "                \n",
    "                item+=1     \n",
    "                 \n",
    "        count=0\n",
    "        for i in store.keys():\n",
    "            if store[i]!=[]:\n",
    "                count+=add(len(store[i]))\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        \n",
    "        n = len(dominoes)\n",
    "\n",
    "        for i in range(n):\n",
    "            if dominoes[i][0] < dominoes[i][1]:\n",
    "                dominoes[i] = dominoes[i][1] * 10 + dominoes[i][0]\n",
    "            else:\n",
    "                dominoes[i] = dominoes[i][0] * 10 + dominoes[i][1]\n",
    "\n",
    "        \n",
    "        md = {}\n",
    "    \n",
    "        for i in range(n):\n",
    "            if md.get(dominoes[i], False):\n",
    "                md[dominoes[i]] += 1 \n",
    "            else:\n",
    "                md[dominoes[i]] = 1\n",
    "\n",
    "        total = 0\n",
    "        for item in md:\n",
    "            l = md[item]\n",
    "            total += int(l * (l-1) / 2)          \n",
    "        \n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def numEquivDominoPairs(self,dominoes) -> int:\n",
    "        d = collections.defaultdict(list)\n",
    "        ans = 0\n",
    "        for index,a in enumerate(dominoes):\n",
    "            a.sort()\n",
    "            d[str(a)].append(index)\n",
    "\n",
    "        # 定义排列组合的C(m, n)\n",
    "        def func(m,n):\n",
    "            a=b=result=1\n",
    "            if m<n:\n",
    "                return 0\n",
    "            else:\n",
    "                minNI=min(n,m-n)#使运算最简便\n",
    "                for j in range(0,minNI):\n",
    "                #使用变量a,b 让所用的分母相乘后除以所有的分子\n",
    "                    a=a*(m-j)\n",
    "                    b=b*(minNI-j)\n",
    "                    result=a//b #在此使用“/”和“//”均可，因为a除以b为整数\n",
    "                return result\n",
    "\n",
    "        for i in d:\n",
    "            ans += func(len(d[i]), 2)\n",
    "        return ans            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        n = len(dominoes)\n",
    "        for i in range(n):\n",
    "            if dominoes[i][0] <= dominoes[i][1]:\n",
    "                dominoes[i] = dominoes[i][0]*10 + dominoes[i][1]\n",
    "            else:\n",
    "                dominoes[i] = dominoes[i][1]*10 + dominoes[i][0]\n",
    "        a = collections.Counter(dominoes)\n",
    "        res = 0\n",
    "        for items in a:\n",
    "            res += a[items]*(a[items]-1)/2\n",
    "        return int(res)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: list[list[int]]) -> int:\n",
    "        lis = []\n",
    "        arr = []\n",
    "        res = 0\n",
    "        for i in dominoes:\n",
    "            m = sorted(i)\n",
    "            lis.append(m)\n",
    "        for i in lis:\n",
    "            if i not in arr:\n",
    "                arr.append(i)\n",
    "                m = lis.count(i)\n",
    "                res += (m*(m - 1)) // 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        d=list(map(lambda x:sorted(x),dominoes))\n",
    "        i=0\n",
    "        res=0\n",
    "        temp=[]\n",
    "        while i<len(d):\n",
    "            if d[i] not in temp:\n",
    "                temp.append(d[i])\n",
    "                t=d.count(d[i])\n",
    "                res+=t*(t-1)//2\n",
    "            i+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        dominoes = [sorted(a) for a in dominoes]\n",
    "        dominoes.sort()\n",
    "        i, j = 0, 0\n",
    "        n = len(dominoes)\n",
    "        res = 0\n",
    "        while i < n:\n",
    "            while j < n and  dominoes[i][0] == dominoes[j][0] and dominoes[i][1] == dominoes[j][1]:\n",
    "                j += 1\n",
    "            N = j - i\n",
    "            res += N * (N - 1) // 2\n",
    "            i = j\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        res = []\n",
    "        for dominoe in dominoes:\n",
    "            res.append(sorted(dominoe))\n",
    "        res.sort()\n",
    "        rr = []\n",
    "        a = 1\n",
    "        for i in range(1, len(res)):\n",
    "            if res[i] == res[i - 1] :\n",
    "                a += 1\n",
    "            else :\n",
    "                rr.append(a)\n",
    "                a = 1\n",
    "            if  i==len(res)-1:\n",
    "                rr.append(a)\n",
    "        return sum(int(r * (r - 1) / 2) for r in rr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        d = dict()\n",
    "        new_dominoes = [sorted(i) for i in dominoes]\n",
    "        for i in new_dominoes:\n",
    "            if str(i) not in d:\n",
    "                d[str(i)] = 1\n",
    "            else:\n",
    "                d[str(i)] += 1\n",
    "        \n",
    "        m = 0\n",
    "        for j in [d[i] for i in d]:\n",
    "             m += j*(j-1)/2\n",
    "        return int(m)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        from collections import Counter\n",
    "        dominoes = sorted([tuple(sorted(x)) for x in dominoes])\n",
    "        d = Counter(dominoes)\n",
    "        res = 0\n",
    "        for k, v in d.items():\n",
    "            res += v*(v-1)//2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes) -> int:\n",
    "        res = 0\n",
    "        dominoes = sorted(map(sorted,dominoes))\n",
    "        dominoes.append([10,11])\n",
    "        pre = dominoes[0]\n",
    "        count = 1\n",
    "        for i in range(1,len(dominoes)):\n",
    "            if dominoes[i][0]==pre[0] and dominoes[i][1]==pre[1]:\n",
    "                count +=1\n",
    "            else:\n",
    "                res+=((count*(count-1))//2)\n",
    "                pre=dominoes[i]\n",
    "                count=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        #执行用时：80 ms, 在所有 Python3 提交中击败了17.87%的用户内存消耗：23.7 MB, 在所有 Python3 提交中击败了5.31%的用户\n",
    "        # res = []\n",
    "        # for dominoe in dominoes:\n",
    "        #     res.append(sorted(dominoe))\n",
    "        # res.sort()\n",
    "        # rr = []\n",
    "        # a = 1\n",
    "        # for i in range(1, len(res)):\n",
    "        #     if res[i] == res[i - 1] :\n",
    "        #         a += 1\n",
    "        #     else :\n",
    "        #         rr.append(a)\n",
    "        #         a = 1\n",
    "        #     if  i==len(res)-1:\n",
    "        #         rr.append(a)\n",
    "        # return sum(int(r * (r - 1) / 2) for r in rr)\n",
    "\n",
    "        res = []\n",
    "        for dominoe in dominoes:\n",
    "            res.append(sorted(dominoe))\n",
    "        res.sort()\n",
    "        rr=0\n",
    "        n=len(res)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if res[j]==res[i]:\n",
    "                    rr+=1\n",
    "                else:\n",
    "                    break\n",
    "        return rr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        n=len(dominoes)\n",
    "        for i in range(n):\n",
    "            if dominoes[i][0]>dominoes[i][1]:\n",
    "                dominoes[i][0],dominoes[i][1]=dominoes[i][1],dominoes[i][0]\n",
    "            dominoes[i]=tuple(dominoes[i])\n",
    "        cnt=Counter(dominoes)\n",
    "        print(cnt)\n",
    "        ans=0\n",
    "        for k in cnt:\n",
    "            v=cnt[k]\n",
    "            ans+=v*(v-1)//2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        nums = [sorted([i, j]) for i, j in dominoes]\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        pre_a, pre_b = -1, -1\n",
    "        tmp = 1\n",
    "        # print(nums)\n",
    "        for i in range(len(nums)):\n",
    "            a, b = nums[i][0], nums[i][1]\n",
    "            if a == pre_a and b == pre_b:\n",
    "                tmp += 1\n",
    "            else:\n",
    "                pre_a = a\n",
    "                pre_b = b\n",
    "                ans += tmp * (tmp - 1) // 2\n",
    "                tmp = 1\n",
    "        ans += (tmp - 1) * tmp // 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        for i in range(len(dominoes)):\n",
    "            dominoes[i] = tuple(sorted(dominoes[i]))\n",
    "        \n",
    "        cnt = collections.Counter(dominoes)\n",
    "        ans = 0\n",
    "        for n in cnt.values():\n",
    "            ans += n * (n - 1) // 2\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        for i in range(len(dominoes)):\n",
    "            dominoes[i] = tuple(sorted(dominoes[i]))\n",
    "        \n",
    "        cnt = collections.Counter(dominoes)\n",
    "        ans = 0\n",
    "        for n in cnt.values():\n",
    "            ans += n * (n - 1) // 2\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        count = collections.defaultdict(int)\n",
    "        for dom in dominoes:\n",
    "            dom.sort()\n",
    "            count[tuple(dom)] += 1\n",
    "        res = 0\n",
    "        for val in count.values():\n",
    "            res += val*(val-1)/2\n",
    "\n",
    "        return int(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        nums = [0] * 100\n",
    "        count = 0\n",
    "        for a, b in dominoes:\n",
    "            idx = a * 10 + b if a <= b else b * 10 + a\n",
    "            count += nums[idx]\n",
    "            nums[idx] += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        dominoes=sorted(map(sorted,dominoes))\n",
    "        n=len(dominoes)\n",
    "        cnts=[]\n",
    "        st=0\n",
    "        for i in range(n):\n",
    "            if dominoes[i]!=dominoes[st]:\n",
    "                if i-st>1:\n",
    "                    cnts.append(i-st)\n",
    "                st=i\n",
    "        if n-st>1:\n",
    "            cnts.append(n-st)\n",
    "        res=0\n",
    "        for cnt in cnts:\n",
    "            res+=cnt*(cnt-1)//2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        dominoes=sorted(map(sorted,dominoes))\n",
    "        dominoes+=[\"\"]\n",
    "        n=len(dominoes)\n",
    "        cnts=[]\n",
    "        st=0\n",
    "        for i in range(n):\n",
    "            if dominoes[i]!=dominoes[st]:\n",
    "                if i-st>1:\n",
    "                    cnts.append(i-st)\n",
    "                st=i\n",
    "        res=0\n",
    "        for cnt in cnts:\n",
    "            res+=cnt*(cnt-1)//2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        temp = []\n",
    "        for item in dominoes:\n",
    "            temp.append((min(item),max(item)))\n",
    "\n",
    "        count = Counter(temp)\n",
    "        ans = 0\n",
    "        for k,v in count.items():\n",
    "            ans += v * (v - 1) // 2\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        dominoes=[sorted(x) for x in dominoes]\n",
    "        dominoes.sort()\n",
    "        def t(n):\n",
    "            tmp=0\n",
    "            for i in range(1,n):\n",
    "                tmp+=i\n",
    "            return tmp\n",
    "        res=0 \n",
    "        temp=1\n",
    "        for i in range(1,len(dominoes)):\n",
    "            \n",
    "            if dominoes[i]==dominoes[i-1]:\n",
    "                temp+=1\n",
    "                if i==len(dominoes)-1:\n",
    "                    if temp>1:\n",
    "                        res+=t(temp)\n",
    "            else:\n",
    "                if temp>1:\n",
    "                    res+=t(temp)\n",
    "                temp=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        counter = Counter([(d[0], d[1]) if (d[0] <= d[1]) else (d[1], d[0]) for d in dominoes])\n",
    "        ans = 0\n",
    "        for d in counter:\n",
    "            t = counter[d]\n",
    "            ans += t * (t - 1) // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        return sum(n*(n-1)//2 for n in Counter(min(a,b)*10+max(a,b) for a,b in dominoes).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        data = {}\n",
    "        for domino in dominoes:\n",
    "            temp = (min(domino),max(domino))\n",
    "            if temp in data:\n",
    "                data[temp] += 1\n",
    "            else:\n",
    "                data[temp] = 1\n",
    "        res = 0\n",
    "        for val in data.values():\n",
    "            res += val * (val-1) // 2\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        ans = 0\n",
    "        for j in [tuple(i) if i[0] <= i[1] else tuple(i[::-1]) for i in dominoes]:\n",
    "            ans += cnt[j]\n",
    "            cnt[j] += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
